/**
 * 链表。部分参考linux的双链表实现。
 */

#ifndef _AHAMOLETT_CLANG_DATASTRUCT_LIST_H_
#define _AHAMOLETT_CLANG_DATASTRUCT_LIST_H_
#ifdef __cplusplus
extern "C" {
#endif

#include <cds/cds_types.h>

/* 双向链表的结构体。双向链表的节点同时作为根节点和普通节点。 */
struct list_head {
    struct list_head    *prev;  /// 指向上一个链表节点
    struct list_head    *next;  /// 指向下一个链表节点
};


/**
 * @brief 获得链表节点所在的结构体指针。
 * 
 * 链表节点一般存在与一个更大的结构体内，该函数是对container_of的封装，作用是得到链表节点所在
 * 的这个结构体的指针。
 * 
 * @param ptr 链表节点的指针。
 * @param type 链表节点所在结构体的类型。
 * @param member 链表节点在其所在结构体内的成员名。
 * 
 * @return type* 链表节点所在结构体的指针
 */
#define list_entry(ptr, type, member)   container_of(ptr, type, member)

/**
 * @brief 得到下一个链表节点。
 */
#define list_next_node(node)    ((node)->next)

/**
 * @brief 得到上一个链表节点。
 */
#define list_prev_node(node)    ((node)->prev)

/**
 * @brief 得到下一个链表节点，如果所给的节点已经是最后一个节点，则返回NULL。
 * 
 * 在 list_next_node() 的基础上，检查传入的节点是否为空，并检查得到的下一个节点是否为
 * 头结点。若满足上面任意一个条件，说明当前节点已经是尾节点，或者无效，则返回NULL。如果还有
 * 下一个节点，则返回下一个节点的指针。
 * 
 * @param head 链表头。
 * @param node 当前链表节点。
 * 
 * @return struct list_head* 下一个节点的指针或者NULL
 */
static inline struct list_head*
list_next_node_safe(struct list_head *head, struct list_head *node)  
{
    struct list_head *__node = NULL;
    if ((node) != NULL) {
        __node = list_next_node(node);
        if (__node == (head)) {
            __node = NULL;
        }
    }
    return __node;
}

/**
 * @brief 得到上一个链表节点，如果所给的节点已经是第一个节点，则返回NULL。
 * 
 * 在 list_prev_node() 的基础上，检查传入的节点是否为空，并检查得到的上一个节点是否为
 * 头结点。若满足上面任意一个条件，说明当前节点已经是头节点，或者无效，则返回NULL。如果还有
 * 上一个节点，则返回上一个节点的指针。
 * 
 * @param head 链表头。
 * @param node 当前链表节点。
 * 
 * @return struct list_head* 上一个节点的指针或者NULL
 */
static inline struct list_head*
list_prev_node_safe(struct list_head *head, struct list_head *node)  
{
    struct list_head *__node = NULL;
    if ((node) != NULL) {
        __node = list_prev_node(node);
        if (__node == (head)) {
            __node = NULL;
        }
    }
    return __node;
}

/**
 * @brief 检查当前节点是否为空节点。
 * 
 * 对于空链表节点的定义是，节点内prev和next指针均指向自身。
 * 
 * @param head 链表节点指针。
 * 
 * @retval true 当前节点是空节点。
 * @retval false 当前节点非空。
 */
#define list_empty(head)    \
    (list_next_node(head) == (head) && list_prev_node(head) == (head))

/**
 * @brief 获取链表的首节点
 */
#define list_first_node(head)   list_next_node(head)

/**
 * @brief 获取链表的尾节点
 */
#define list_last_node(head)    list_prev_node(head)

/**
 * @brief 获取链表的首节点，若给定链表头没有首节点返回NULL。
 * 
 * @param head 链表头节点的指针。
 * 
 * @return struct list_head* 有首节点返回首节点的地址，否则返回NULL。
 */
#define list_first_node_safe(head)   list_next_node_safe(head, head)

/**
 * @brief 获取链表的尾节点，若给定链表头没有尾节点返回NULL。
 * 
 * @param head 链表头节点的指针。
 * 
 * @return struct list_head* 有尾节点返回首节点的地址，否则返回NULL。
 */
#define list_last_node_safe(head)    list_prev_node_safe(head, head)

/**
 * @brief 判断给定节点是不是首节点。
 * 
 * @param head node所在链表的链表头。
 * @param node 进行判断的链表节点。
 * 
 * @retval true node是首节点。
 * @retval false node不是首节点。
 */
#define list_is_first(head, node)   \
    ((node) != NULL && list_first_node_safe(head) == (node))

/**
 * @brief 判断给定节点是不是尾节点。
 * 
 * @param head node所在链表的链表头。
 * @param node 进行判断的链表节点。
 * 
 * @retval true node是尾节点。
 * @retval false node不是尾节点。
 */
#define list_is_last(head, node)    \
    ((node) != NULL && list_last_node_safe(head) == (node))

/**
 * @brief 顺序遍历链表。
 * 
 * 利用宏对for语句进行封装，从首节点到尾节点依次遍历整个链表。
 * 
 * @warning 遍历过程中不要更改pos内的指针，否则会出错。如果需要在遍历的过程中操作pos的内容，
 *          请使用list_foreach_safe。
 * 
 * @param head struct list_head* 链表头结点。
 * @param pos struct list_head* 作为游标用于遍历整个链表。
 */
#define list_foreach(head, pos)    \
    for (   (pos) = list_first_node(head);  \
            (pos) != (head);    \
            (pos) = list_next_node(pos))
/**
 * @brief 逆序遍历链表。
 * 
 * 利用宏对for语句进行封装，从尾节点到首节点依次遍历整个链表。
 * 
 * @warning 遍历过程中不要更改pos内的指针，否则会出错。如果需要在遍历的过程中操作pos的内容，
 *          请使用list_foreach_safe_inv。
 * 
 * @param head struct list_head* 链表头结点。
 * @param pos struct list_head* 作为游标用于遍历整个链表。
 */
#define list_foreach_inv(head, pos)    \
    for (   (pos) = list_last_node(head);  \
            (pos) != (head);    \
            (pos) = list_prev_node(pos))

/**
 * @brief 更安全的方式顺序遍历链表。
 * 
 * 利用宏对for语句进行封装，从尾节点到首节点依次遍历整个链表，并通过n指针保证遍历过程中对pos
 * 的修改不会导致循环出错。
 * 
 * @param head struct list_head* 链表头结点。
 * @param pos struct list_head* 作为游标用于遍历整个链表。
 * @param n struct list_head* 和pos一样作为游标用于遍历整个链表。
 */
#define list_foreach_safe(head, pos, n) \
    for (   (pos) = list_first_node_safe(head),  \
            (n) = list_next_node_safe((head), (pos));    \
            (pos) != NULL;  \
            (pos) = (n), (n) = list_next_node_safe((head), (n)))

/**
 * @brief 更安全的方式逆序遍历链表。
 * 
 * 利用宏对for语句进行封装，从首节点到尾节点依次遍历整个链表，并通过n指针保证遍历过程中对pos
 * 的修改不会导致循环出错。
 * 
 * @param head struct list_head* 链表头结点。
 * @param pos struct list_head* 作为游标用于遍历整个链表。
 * @param n struct list_head* 和pos一样作为游标用于遍历整个链表。
 */
#define list_foreach_safe_inv(head, pos, n) \
    for (   (pos) = list_last_node_safe(head),   \
            (n) = list_prev_node_safe((head), (pos));    \
            (pos) != NULL;  \
            (pos) = (n), (n) = list_prev_node_safe((head), (n)))

/**
 * @brief 获得下一个链表节点所在的结构体指针。
 * 
 * 给定当前链表节点所在的结构体指针，得到下一个链表节点所在的结构体指针。同时也会判断有没有
 * 下一个链表节点，如果没有则返回NULL。
 * 
 * @param head struct list_head* 链表的头结点指针。
 * @param node type* 当前链表节点所在的结构体指针。
 * @param member 链表节点在其所在结构体内的成员名称。
 * 
 * @return type* 如果有下一个节点返回下一个节点所在结构体的指针，否则返回NULL。
 */
#define list_next_entry_safe(head, node, member)   ({  \
    typeof(*(node)) *__entry = NULL;    \
    struct list_head *__node =  \
        list_next_node_safe((head), &(node)->member);  \
    if (__node != NULL) {   \
        __entry = list_entry(__node, typeof(*(node)), member);  \
    }   \
    __entry;    \
})

/**
 * @brief 获得上一个链表节点所在的结构体指针。
 * 
 * 给定当前链表节点所在的结构体指针，得到上一个链表节点所在的结构体指针。同时也会判断有没有
 * 上一个链表节点，如果没有则返回NULL。
 * 
 * @param head struct list_head* 链表的头结点指针。
 * @param node type* 当前链表节点所在的结构体指针。
 * @param member 链表节点在其所在结构体内的成员名称。
 * 
 * @return type* 如果有上一个节点返回上一个节点所在结构体的指针，否则返回NULL。
 */
#define list_prev_entry_safe(head, node, member)   ({  \
    typeof(*(node)) *__entry = NULL;    \
    struct list_head *__node =  \
        list_prev_node_safe((head), &(node)->member);  \
    if (__node != NULL) {   \
        __entry = list_entry(__node, typeof(*(node)), member);   \
    }   \
    __entry;    \
})

/**
 * @brief 获得链表中首个链表节点所在的结构体指针。
 * 
 * 给定一个链表的头结点指针，得到这个链表的首节点所在结构体指针。同时也会判断链表是否有首节点，
 * 如果没有则返回NULL。
 * 
 * @param head struct list_head* 链表的头结点指针。
 * @param type 链表节点所在结构体的类型。
 * @param member 链表节点在其所在结构体内的成员名称。
 * 
 * @return type* 如果有首节点返回首节点所在结构体的指针，否则返回NULL。
 */
#define list_first_entry_safe(head, type, member)   ({ \
    struct list_head *__node = list_first_node_safe(head);   \
    type *__target_ptr = NULL;  \
    if (__node != NULL) {   \
        __target_ptr = list_entry(__node, type, member);    \
    }   \
    __target_ptr;   \
})

/**
 * @brief 获得链表中末尾链表节点所在的结构体指针。
 * 
 * 给定一个链表的头结点指针，得到这个链表的尾节点所在结构体指针。同时也会判断链表是否有尾节点，
 * 如果没有则返回NULL。
 * 
 * @param head struct list_head* 链表的头结点指针。
 * @param type 链表节点所在结构体的类型。
 * @param member 链表节点在其所在结构体内的成员名称。
 * 
 * @return type* 如果有尾节点返回尾节点所在结构体的指针，否则返回NULL。
 */
#define list_last_entry_safe(head, type, member) ({ \
    struct list_head *__node = list_last_node_safe(head);   \
    type *__target_ptr = NULL;  \
    if (__node != NULL) {   \
        __target_ptr = list_entry(__node, type, member);    \
    }   \
    __target_ptr;   \
})

/**
 * @brief 更安全的方式顺序遍历链表内所有节点的entry。
 * 
 * 对for循环的封装，顺序遍历整个链表内所有链表节点所在的结构体。
 * 
 * @param head struct list_head* 链表的头结点指针。
 * @param pos type* 作为游标存放链表节点所在结构体的指针，遍历整个链表。
 * @param n type* 和pos一样的作用。
 * @param member 链表节点在其所在结构体内的成员名称。
 */
#define list_foreach_entry_safe(head, pos, n, member)   \
    for (   (pos) = list_first_entry_safe(   \
                (head), typeof(*(pos)), member),    \
            (n) = list_next_entry_safe(  \
                (head), (pos), member); \
            (pos) != NULL;  \
            (pos) = (n),    \
            (n) = list_next_entry_safe(  \
                (head), (n), member))

/**
 * @brief 更安全的方式逆序遍历链表内所有节点的entry。
 * 
 * 对for循环的封装，逆序遍历整个链表内所有链表节点所在的结构体。
 * 
 * @param head struct list_head* 链表的头结点指针。
 * @param pos type* 作为游标存放链表节点所在结构体的指针，遍历整个链表。
 * @param n type* 和pos一样的作用。
 * @param member 链表节点在其所在结构体内的成员名称。
 */
#define list_foreach_entry_safe_inv(head, pos, n, member)   \
    for (   (pos) = list_last_entry_safe(   \
                (head), typeof(*(pos)), member),    \
            (n) = list_prev_entry_safe(  \
                (head), (pos), member); \
            (pos) != NULL;  \
            (pos) = (n),    \
            (n) = list_prev_entry_safe(  \
                (head), (n), member))

/**
 * @brief 初始化链表节点
 * 
 * @param head  链表头
 */
static inline void
list_head_init(struct list_head *head)
{
    head->next = head;
    head->prev = head;
}

static inline void
__list_link_nodes(
    struct list_head *node1, 
    struct list_head *node2
)
{
    node1->next = node2;
    node2->prev = node1;
}

/**
 * @brief 删除链表节点
 * 
 * @param head  链表头
 */
static inline void
list_del(struct list_head *head)
{
    __list_link_nodes(head->prev, head->next);
}

/**
 * @brief 删除并初始化链表节点
 * 
 * @param head  链表头
 */
static inline void
list_del_init(struct list_head *head)
{
    list_del(head);
    list_head_init(head);
}

static inline void
__list_insert_node(
    struct list_head *prev, 
    struct list_head *node, 
    struct list_head *next
)
{
    __list_link_nodes(prev, node);
    __list_link_nodes(node, next);
}

/**
 * @brief 将一个节点加入链表，作为其首节点。
 * 
 * @param head 链表头结点
 * @param node 被插入的链表节点
 */
static inline void
list_add(struct list_head *head, struct list_head *node)
{
    __list_insert_node(head, node, head->next);
}

/**
 * @brief 将一个节点加入链表，作为其尾节点。
 * 
 * @param head 链表头结点
 * @param node 被插入的链表节点
 */
static inline void
list_add_tail(struct list_head *head, struct list_head *node)
{
    __list_insert_node(head->prev, node, head);
}

/**
 * @brief 交换两个链表节点的位置。
 * 
 * @param node1 链表节点
 * @param node2 链表节点
 */
static inline void
list_exchange_nodes(
    struct list_head *node1, 
    struct list_head *node2
)
{
    struct list_head *__prev = node1->prev;
    struct list_head *__next = node1->next;
    
    __list_insert_node(node2->prev, node1, node2->next);
    __list_insert_node(__prev, node2, __next);
}

/**
 * @brief 将一个链表节点移动到给定链表的最开始处。
 * 
 * @param head 链表头结点。
 * @param node 链表节点。
 */
static inline void
list_move(struct list_head *head, struct list_head *node)
{
    list_del(node);
    list_add(head, node);
}

/**
 * @brief 将一个链表节点移动到给定链表的最末尾处。
 * 
 * @param head 链表头结点。
 * @param node 链表节点。
 */
static inline void
list_move_tail(struct list_head *head, struct list_head *node)
{
    list_del(node);
    list_add_tail(head, node);
}

#ifdef __cplusplus
}
#endif
#endif  // #ifndef _AHAMOLETT_CLANG_DATASTRUCT_LIST_H_
